1506. Пересекающиеся лестницы

Вдоль узкой улицы по обе стороны расположены дома. Лестница длиной x футов расположена так, что ее низ упирается в основание дома на правой стороне, а верх прислонен к дому на левой стороне улицы. Аналогично низ лестницы длиной y футов упирается в основание дома на левой стороне, а верх прислонен к правому дому. Точка, в которой пересекаются лестницы, находится в точности c футов над землей. Какова ширина улицы?

Вход. Каждая строка содержит три положительных действительных числа x, y и c.

Выход. Для каждого теста в отдельной строке вывести одно действительное число с тремя десятичными знаками – ширину улицы.

Пример входа	Пример выхода
30 40 10 12.619429 8.163332 3 10 10 3 10 10 1	26.033 7.000 8.000 9.798

РЕШЕНИЕ

геометрия - бинарный поиск

Анализ алгоритма

Треугольники AOP и ADC подобны: .

Треугольники COP и CBA подобны: .

. Откуда , .

Будем искать искомую ширину улицы d = AC бинарным поиском.

Изначально положим 0 ≤ d ≤ min(x, y). По имеющимся d, x, y находим a, b и c. Чем больше d (при фиксированных x, y), тем меньше c.

Реализация алгоритма

Читаем входные данные для каждого теста.

while(scanf("%lf %lf %lf",&x,&y,&c) == 3)

{

Установим left = 0, right = min(x,y). Далее в цикле будет иметь место неравенство left ≤ d ≤ right.

left = 0;

if (x < y) right = x; else right = y;

d = (left + right) / 2;

do

{

Вычисляем значения a, b, c.

a = sqrt(x*x - d*d); b = sqrt(y*y - d*d);

c1 = 1/(1/a + 1/b);

Если найденное значение c1 меньше искомого с, то необходимо уменьшить верхнюю границу d. Иначе следует увеличить его нижнюю границу.

if (c1 < c) right = (left + right) / 2;

else left = (left + right) / 2;

d = (left + right) / 2;

Вычисления проводим до требуемой в условии задачи точности (четыре десятичных знака).

} while (fabs(c1 - c) > 0.00001);

Выводим результат.

printf("%.3lf\n",d);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

con.useLocale(new Locale("US"));

while(con.hasNext())

{

double x = con.nextDouble();

double y = con.nextDouble();

double c = con.nextDouble();

double Left = 0, Right, a, b, c1;

if (x < y) Right = x; else Right = y;

double d = (Left + Right) / 2;

do

{

a = Math.sqrt(x*x - d*d);

b = Math.sqrt(y*y - d*d);

c1 = 1/(1/a + 1/b);

if (c1 < c) Right = (Left + Right) / 2;

else Left = (Left + Right) / 2;

d = (Left + Right) / 2;

} while (Math.abs(c1 - c) > 0.00001);

System.out.format(Locale.US,"%.3f\n",d);

}

}

}